<?php
/**
 * @title 面试题 17.13. 恢复空格 - 递归
 * @author start2004
 */

class Solution {

    /**
     * @param String[] $dictionary
     * @param String $sentence
     * @return Integer
     */
    function respace($dictionary, $sentence) {
        /**
         * @since 2020-07-23 哈希字典
         */
        $dictHash = [];
        foreach ($dictionary as $word){
            $dictHash[$word] = 1;
        }

        /**
         * @since 2020-07-23 哈希缓存
         */
        $this->dps = [];

        /**
         * @return
         */
        return self::find($dictHash, $sentence);
    }

    /**
     * @title 返回未识别字符最少数量
     * @author start2004
     * @since 2020-07-23 Created
     *
     * @param array $dictHash
     * @param string $sentence
     */
    function find($dictHash = [], $sentence = ''){
        if(isset($this->dps[$sentence])){
            return $this->dps[$sentence];
        } else {}

        /**
         * @since 2020-07-23 文章长度
         */
        $len = strlen($sentence);

        /**
         * @since 2020-07-23 未知字符数
         */
        $unknowCount = [];

        /**
         * @since 2020-07-23 空字符串
         */
        if($len == 0){
            $min = 0;
        } elseif($len == 1){
            /**
             * @since 2020-07-23 只有1个长度
             */
            if(isset($dictHash[$sentence])){
                $min = 0;
            } else {
                $min = 1;
            }
        } else {
            /**
             * @since 2020-07-23 完整匹配, 结束
             */
            if(isset($dictHash[$sentence])){
                $min = 0;
            } else {
                /**
                 * @since 2020-07-23 超时递归
                 */
                for($l=1; $l<$len; $l++){
                    $tryWord = substr($sentence, 0, $l);

                    if(isset($dictHash[$tryWord])){
                        $unknowCount[] = self::find($dictHash, substr($sentence, $l));
                    } else {}
                }

                /**
                 * @since 2020-07-23 最小值<=1, 无法更短
                 */
                if($unknowCount){
                    $min = min($unknowCount);
                    if($min>1){
                        $min = min($min, 1+self::find($dictHash, substr($sentence, 1)));
                    } else {}
                } else {
                    /**
                     * @since 2020-07-23 没有匹配成功的, 最少未知字符1个
                     */
                    $min = 1+self::find($dictHash, substr($sentence, 1));
                }
            }
        }
        $this->dps[$sentence] = $min;

        /**
         * @return
         */
        return $min;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.23_7.php
 */
$datas = [
    [["frrrbbrrbfrfqqbbbrb","qr","b","rf","qqbbbbfrqbrrqrffbrqqqbqqfqfrr","r","ffqq","bffbqfqqbrrrf","fq","qfr","fr","rqrrbfbfq","r","f","qbqbrbrbqfqbbbfbbbfbq","bqqbbbqrbbrf","f"], "bqqffbqbbfqrfrrrbbrrbfrfqqbbbrbfqfffffrfqfqfffffrrfqfrrqbqfrbfrqqrfrbrbbqbqbqqfqrfbfrfr"], // 9

    // [["looked","just","like","her","brother"], "jesslookedjustliketimherbrother"], // 7
    //
    // [["right", "righting"], "rightinglobal",], // 5, 优先最短匹配会出问题
    //
    // [["right", "righting", "global"], "rightinglobal"], // 2, 优先最长匹配会出问题
    //
    // [["right", "righting", "tinglobal"], "rightinglobal"], // 4, 优先最长和最短匹配混用也会出问题
    //
    // [["right", "global","tinglobal"], "rightinglobal"], // 2
    //
    // [["right", "righting", "global", "ightin"], "rightinglobal"], // 1
    //
    // [["right", "righting", "righ", "tin", "ri", "global"], "rightinglobal"], // 0
    //
    // [["right", "righting", "ri", "h", "global"], "rightinglobal"], // 2

];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->respace($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
